
Namespace std
    'same as xtree, just make a confirm
    Public Class heap(Of valueType As IComparable(Of valueType))
        Implements ICloneable, IComparable

        Public Const head As Int64 = 0
        Public Const npos As Int64 = -1
        Public Const dataSegSize As Int64 = 1024
        Private _data As vector(Of valueType)

        Private Shared Function father(ByVal index As Int64) As Int64
            Return (index - 1) >> 1
        End Function

        Private Shared Function leftChild(ByVal index As Int64) As Int64
            Return (index << 1) + 1
        End Function

        Private Shared Function rightChild(ByVal index As Int64) As Int64
            Return leftChild(index) + 1
        End Function

        Protected Overridable Function swap(ByVal first As Int64, ByVal second As Int64) As Boolean
            If first = second Then
                Return availableIndex(first)
            ElseIf availableIndex(first) AndAlso availableIndex(second) Then
                base.swap(_data(first), _data(second))
                Return True
            Else
                Return False
            End If
        End Function

        Private Function up(ByVal index As Int64) As Int64
            If Not (availableIndex(index)) Then
                Return npos
            Else
                Dim parent As Int64 = npos
                While (True)
                    parent = father(index)
                    If Not (availableIndex(parent)) Then
                        Exit While
                    Else
                        debugassert(index >= parent _
                                    , "got an invalid parent " + Convert.ToString(parent) _
                                    + " index " + Convert.ToString(index))
                        If index > parent AndAlso compare(_data(index), _data(parent)) > 0 Then
                            debugassert(swap(index, parent) _
                                        , Convert.ToString(index) + " or " _
                                        + Convert.ToString(parent) + " is not in heap.")
                            index = parent
                        Else
                            Exit While
                        End If
                    End If
                End While

                debugassert(availableIndex(index), "up function makes an index not available.")
                Return index
            End If
        End Function

        Private Function down(ByVal index As Int64) As Int64
            If Not (availableIndex(index)) Then
                Return npos
            Else
                Dim min As Int64 = head
                Dim left As Int64 = head
                Dim right As Int64 = head
                While (True)
                    min = index
                    left = leftChild(index)
                    right = rightChild(index)
                    If availableIndex(left) Then
                        If compare(_data(left), _data(min)) > 0 Then
                            min = left
                        End If
                    End If
                    If availableIndex(right) Then
                        If compare(_data(right), _data(min)) > 0 Then
                            min = right
                        End If
                    End If

                    If min <> index Then
                        debugassert(swap(index, min) _
                                    , Convert.ToString(index) + " or " + Convert.ToString(min) + " is not in heap.")
                        index = min
                    Else
                        Exit While
                    End If
                End While

                debugassert(availableIndex(index), "down function makes an index not available.")
                Return index
            End If
        End Function

        Public Function availableIndex(ByVal index As Int64) As Boolean
            Return _data.availableIndex(index)
        End Function

        Public Function empty() As Boolean
            Return _data.empty()
        End Function

        Public Overridable Function [erase](ByVal index As Int64) As Boolean
            If Not availableIndex(index) Then
                Return False
            End If
            Dim tail As valueType = Nothing
            pop_back(tail)
            If index <> size() Then
                update(index, tail)
            End If

            Return True
        End Function

        Public Sub pop_front(ByRef value As valueType)
            If empty() Then
                value = Nothing
            Else
                value = _data(head)
                debugassert([erase](head), "erase(head) returns false.")
            End If
        End Sub

        Public Sub pop(ByRef value As valueType)
            pop_front(value)
        End Sub

        Protected Sub pop_back(ByRef value As valueType)
            If empty() Then
                value = Nothing
            Else
                value = _data.back()
                _data.pop_back()
            End If
        End Sub

        Public Function insert(ByVal value As valueType) As Int64
            _data.insert(Nothing)
            Return update(_data.size() - 1, value)
        End Function

        Public Function seek(ByRef index As Int64, ByVal newIndex As Int64) As Boolean
            index = newIndex
            Return True
        End Function

        Public Function take(ByVal index As Int64, ByRef value As valueType) As Boolean
            Return _data.take(index, value)
        End Function

        Public Function [next](ByRef index As Int64) As Boolean
            index += 1
            If availableIndex(index) Then
                Return True
            Else
                Return False
            End If
        End Function

        Public Function prev(ByRef index As Int64) As Boolean
            index -= 1
            If availableIndex(index) Then
                Return True
            Else
                Return False
            End If
        End Function

        Public Sub New()
            clear()
        End Sub

        Public Overridable Sub clear()
            If _data Is Nothing Then
                _data = New vector(Of valueType)
            Else
                _data.clear()
            End If
        End Sub

        Public Function begin() As Int64
            Return head
        End Function

        Public Function [end]() As Int64
            Return _data.size
        End Function

        Public Overridable Function update(ByVal index As Int64, ByVal value As valueType) As Int64
            Dim rtn As Int64
            If availableIndex(index) Then
                copy(_data(index), value)
                rtn = up(index)
                If rtn = index Then
                    rtn = down(index)
                End If
                Return rtn
            Else
                Return npos
            End If
        End Function

        Default Public Property at(ByVal index As Int64) As valueType
            Get
                Dim value As valueType = Nothing
                take(index, value)
                Return value
            End Get
            Set(ByVal value As valueType)
                update(index, value)
            End Set
        End Property

        Public Function size() As Int64
            Return _data.size
        End Function

        Public Function clone() As Object Implements System.ICloneable.Clone
            Dim rtn As heap(Of valueType)
            rtn = alloc(Me)
            copy(rtn._data, _data)
            Return rtn
        End Function

        Public Shared Operator <>(ByVal this As heap(Of valueType), ByVal that As heap(Of valueType)) As Boolean
            Return Not this = that
        End Operator

        Public Shared Operator =(ByVal this As heap(Of valueType), ByVal that As heap(Of valueType)) As Boolean
            If this Is Nothing AndAlso that Is Nothing Then
                Return True
            ElseIf this Is Nothing OrElse that Is Nothing Then
                Return False
            Else
                Return compare(this, that) = 0
            End If
        End Operator

        Public Function CompareTo(ByVal obj As Object) As Integer Implements System.IComparable.CompareTo
            Dim right As heap(Of valueType) = Nothing
            right = convertor.cast(Of heap(Of valueType))(obj)

            If size() <> right.size() Then
                Return size() - right.size()
            Else
                Return compare(_data, right._data)
            End If
        End Function

        Public Overrides Function ToString() As String
            Return Convert.ToString(_data)
        End Function

        Private Class unittestInfo
            Public heap As heap(Of valueType) = Nothing
            Public keys As vector(Of valueType) = Nothing

            Public Sub New()
                heap = New heap(Of valueType)()
                keys = New vector(Of valueType)()
            End Sub
        End Class

        Private Class unittestActions
            Private Shared Sub parseParameter(ByVal obj As Object _
                                              , ByRef heap As heap(Of String) _
                                              , ByRef keys As vector(Of String))
                Dim info As heap(Of String).unittestInfo = Nothing
                info = convertor.cast(Of heap(Of String).unittestInfo)(obj)
                heap = info.heap
                keys = info.keys
                assert(Not heap Is Nothing, "heap is nothing.")
                assert(Not keys Is Nothing, "keys is nothing.")
            End Sub

            Public Shared Sub insert(ByVal obj As Object)
                Dim heap As heap(Of String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, heap, keys)

                Dim s As String = Nothing
                s = createGUID()
                Dim rtn As Int64
                rtn = heap.insert(s)
                keys.insert(s)
                raiseError("insert " + s)
                assert(strsame(heap(rtn), s, True), "heap(" + Convert.ToString(rtn) + ") <> " + s)
            End Sub

            Public Shared Sub [erase](ByVal obj As Object)
                Dim heap As heap(Of String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, heap, keys)

                If Not keys.empty() Then
                    Dim i As Int64
                    i = rnd(0, keys.size(), True)
                    Dim k As String = Nothing
                    copy(k, heap(i))
                    assert(heap.erase(i), "heap.erase(" + Convert.ToString(i) + ") returns false.")
                    assert(Not strsame(heap(i), k, True), "heap(" + Convert.ToString(i) + ") = " + k)
                    raiseError("erase " + k + " at " + Convert.ToString(i))
                    keys.erase(k)
                Else
                    assert(heap.empty(), "heap.empty() <> keys.empty().")
                End If
            End Sub

            Public Shared Sub pop_front(ByVal obj As Object)
                Dim heap As heap(Of String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, heap, keys)

                If Not keys.empty() Then
                    Dim s As String = Nothing
                    heap.pop_front(s)
                    assert(keys.erase(s), "keys.erase(" + s + ") returns false.")
                    raiseError("pop_front " + s)
                Else
                    assert(heap.empty(), "heap.empty() <> keys.empty().")
                End If
            End Sub

            Public Shared Sub clone(ByVal obj As Object)
                Dim heap As heap(Of String) = Nothing
                parseParameter(obj, heap, Nothing)

                Dim info As heap(Of String).unittestInfo = Nothing
                info = convertor.cast(Of heap(Of String).unittestInfo)(obj)
                Dim oldheap As heap(Of String) = Nothing
                oldheap = info.heap
                info.heap = Nothing
                copy(info.heap, heap)
                assert(Not Object.ReferenceEquals(info.heap, oldheap), "cannot clone to a new instance.")
                assert(info.heap.size() = oldheap.size(), "new heap.size()<>oldheap.size().")
                assert(compare(info.heap, oldheap) = 0, "new heap is not the same as old heap.")
                raiseError("clone a same instance with existing one.")
            End Sub

            Public Shared Sub clear(ByVal obj As Object)
                Dim heap As heap(Of String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, heap, keys)

                heap.clear()
                assert(heap.size() = 0, "heap.size()<>0 after clear.")
                keys.clear()
            End Sub
        End Class

        Public Shared Sub automaticalUnittest()
            Dim roundcount As Int64 = 10240
            If isreleasebuild() Then
                roundcount *= 20
            End If

            raiseError("******** automatical heap unitTest *******", errorHandle.errorType.application)

            Dim info As heap(Of String).unittestInfo = Nothing
            info = New heap(Of String).unittestInfo()
            randomrun.invoke(roundcount, info _
                             , New randomrun.info(AddressOf unittestActions.insert, 0.55) _
                             , New randomrun.info(AddressOf unittestActions.erase, 0.2) _
                             , New randomrun.info(AddressOf unittestActions.pop_front, 0.15) _
                             , New randomrun.info(AddressOf unittestActions.clone, 0.05) _
                             , New randomrun.info(AddressOf unittestActions.clear, 0.05))

            While Not info.heap.empty()
                unittestActions.pop_front(info)
            End While

            raiseError("******* finish automatical unittest ******", errorHandle.errorType.application)
        End Sub
    End Class
End Namespace
